package 单周赛.september;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @
 * @date 2024/03/17
 */
public class 第389场单周赛 {

    public static void main(String[] args) {

        System.out.println(minimumDeletions("itatwtiwwi", 1));
    }

    /**
     * 哈希表模拟
     */
    public boolean isSubstringPresent(String s) {

        Set<String> set = new HashSet<>();
        for (int i = 0; i < s.length() - 1; i++) {
            set.add(s.substring(i, i + 2));
        }

        String s1 = new StringBuilder()
                .append(s)
                .reverse()
                .toString();
        for (int i = 0; i < s1.length() - 1; i++) {
            if (set.contains(s1.substring(i, i + 2))) {
                return true;
            }
        }

        return false;
    }

    /**
     * 前缀和
     * 如果 s.CharAt(i) == c 那么 [i,s.length()-1] 中有多少个 c 就有多少符合条件的字符串
     */
    public long countSubstrings(String s, char c) {
        long ans = 0;
        int[] preSum = new int[s.length() + 1];

        for (int i = 0; i < s.length(); i++) {
            preSum[i + 1] = preSum[i];
            if (s.charAt(i) == c) {
                preSum[i + 1]++;
            }
        }

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                ans += preSum[s.length()] - preSum[i];
            }
        }

        return ans;
    }

    /**
     * 统计+排序+分情况搜索
     * 先统计字符出现的频率，然后从小到大排序
     * 有两种方案：
     * 1，删除最小频率的全部字符
     * 2，删除最大频率-最小频率-k的字符数量
     */
    public static int minimumDeletions(String word, int k) {
        int[] record = new int[26];
        for (char c : word.toCharArray()) {
            record[c - 'a']++;
        }

        Arrays.sort(record);

        int left = 0, right = record.length - 1;

        while (record[left] == 0) {
            left++;
        }

        return dfs(record, left, right, k);
    }

    // [left,right] 使 word 成为 k 特殊字符串 需要删除的字符的最小数量是多少
    private static int dfs(int[] record, int left, int right, int k) {
        if (left >= right) {
            return 0;
        }
        if (record[right] - record[left] <= k) {
            return 0;
        }
        int diff = record[right] - record[left] - k;

        return Math.min(record[left] + dfs(record, left + 1, right, k),
                diff + dfs(record, left, right - 1, k));
    }

}
